package com.leetcode.tree.traversal;

import com.leetcode.basic.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/10/25 15:28
 */
public class Codec_297 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append('#').append(',');
                continue;
            } else {
                sb.append(node.val).append(',');
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.deleteCharAt(sb.length() - 1).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("")) return null;
        String[] nodeStrs = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodeStrs[0]));
        queue.offer(root);
        int index = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) continue;

            String s1 = nodeStrs[index], s2 = nodeStrs[index + 1];
            // 注意一定不能直接跳过#结点，而需要赋值null后入队
            TreeNode left = s1.equals("#") ? null : new TreeNode(Integer.parseInt(s1));
            TreeNode right = s2.equals("#") ? null : new TreeNode(Integer.parseInt(s2));

            node.left = left;
            node.right = right;

            queue.offer(left);
            queue.offer(right);
            index += 2;
        }
        return root;
    }

}
